package com.bigshen.algorithm.dBinarySearch.solution05CutWood;

/**
 * 给定n块不同长度的木头，如 [234,156,789,312] 4块不同长度的木头，
 * 现在需要切木头，切出8块相同长度的木头，切的木头长度力求最长。
 * 求合适的木头长度
 */
public class Solution {

    public int cutWood(int[] array, int piece) {

        if (null == array || array.length == 0 || piece == 0) {
            return 0;
        }

        // 找出最长的一块木头，以其为起始长度，尝试开始切木头，切出的块数不够，则长度减半 --  二分法
        int maxLength = 0;
        for (int len : array) {
            maxLength = maxLength > len ? maxLength : len;
        }

        int start = 1;
        int end = maxLength; // 从maxLength开始切
        int mid = 0;
        while (start + 1 < end) {
            int currentPiece = 0;
            // 首次使用最大长度开始切
            mid = (mid == 0 ? end : (start + (end-start)/2));

            for (int len : array) {
                currentPiece += len/mid;
                if (currentPiece >= piece) {
                    // 已经能切够足够块数，去尝试切更大
                   continue;
                }
            }

            if (currentPiece >= piece) {
                System.out.println(String.format("尝试切的长度 %s，能切出足够块数，尝试切更长 --> ", mid));
                start = mid;
            } else {
                // 切的长度过长，不能切够足够块数，尝试切更短
                System.out.println(String.format("尝试切的长度 %s，不能切出足够块数，尝试切更短 <-- ", mid));
                end = mid;
            }

        }

        if (getPieces(array, start) >= piece) {
            // start满足
            return start;
        }

        if (getPieces(array, end) >= piece) {
            // start满足
            return end;
        }

        return 0;

    }


    public int getPieces(int[] array, int len) {

        int piece = 0;

        for (int wood : array) {
            int curPiece = wood/len;
            piece += curPiece;
        }
        return piece;
    }

    public static void main(String[] args) {

        int[] array = {213,322,321};
        int piece = 5;

        int maxLength = new Solution().cutWood(array, piece);
        System.out.println(maxLength);

        System.out.println("----------------");
        System.out.println(new Solution().getPieces(array, maxLength));
    }

}
